W6. Deterministic Pushdown Automata, Configurations, Pumping Lemma for Context-Free Languages, PDAs and Compilers

1. Summary

1.1 From Finite Automata to Pushdown Automata

We already know that Finite State Automata (FSAs) can recognize regular languages. But FSAs have a fundamental limitation: they have only a fixed, finite amount of memory — precisely the current state. This makes certain languages impossible to recognize, such as \(L = \{a^n b^n \mid n \geq 0\}\), where the machine would need to remember an arbitrarily large count of \(a\)’s.

To go beyond regular languages, we need a model with more memory. The natural extension is to attach a stack to an FSA, producing a Pushdown Automaton (PDA). The name “pushdown” refers to the push-down nature of the stack, where new items are placed on top and the top item is always the one removed first.

From FSA to PDA: the same finite control gains an unbounded stack

Informally:

• FSA = finite control unit (states only)
• PDA = finite control unit + an infinite stack

The hierarchy of computational models, from weakest to most powerful, looks like:

• Combinational logic — no memory
• Finite State Automata — fixed, bounded memory (current state only)
• Pushdown Automata — unbounded stack memory (can grow without limit)
• Turing Machines — full read/write tape (most powerful)

PDAs sit exactly at the level above FSAs and can recognize context-free languages (CFLs), which include most programming language constructs. This is why PDAs are at the heart of compilers — the syntax of programming languages is context-free.

1.2 The Stack: A Refresher

A stack is a last-in, first-out (LIFO) data structure. Think of a stack of trays in a cafeteria: you can only add or remove from the top.

LIFO stack discipline used by PDAs

Operations:

• Push: Place a new symbol on top of the stack.
• Pop: Remove the top symbol from the stack (and “read” it at the same time).

A PDA’s stack starts with a special bottom-of-stack symbol \(Z_0\), which serves as a sentinel marking the bottom. When \(Z_0\) is on top, the stack is effectively empty.

Example — push \(a\), \(b\), \(c\), then pop:

1. Initial stack: \(Z_0\) (bottom only)
2. Push \(a\): stack = \(a, Z_0\) (top to bottom)
3. Push \(b\): stack = \(b, a, Z_0\)
4. Push \(c\): stack = \(c, b, a, Z_0\)
5. Pop: removes \(c\); stack = \(b, a, Z_0\)

The most recently pushed symbol is always the first to be removed. This LIFO property makes the stack ideal for matching nested structures like balanced parentheses.

Historical note: The concept of a stack was introduced by Alan Turing in his 1946 paper on the Automatic Computing Engine (ACE), where he called the operations BURY and UNBURY, and used them in the theory of subroutines.

1.3 Informal Description of a PDA

A PDA has three components:

1. An input tape — a read-only, left-to-right sequence of symbols (the input string)
2. A finite control unit — like an FSA, it keeps track of the current state
3. A stack of infinite size — the extra memory; the control unit reads the top and replaces it

PDA step: read input, inspect the stack top, then move to a new configuration

In each step, a PDA looks at three things simultaneously:

• The current state \(q\)
• The next input symbol (or \(\varepsilon\) for a “silent” move)
• The top of the stack

Based on these three inputs, it:

1. Moves to a new state \(q'\)
2. Advances the input head (or stays in place for \(\varepsilon\)-moves)
3. Replaces the top stack symbol with some string \(\alpha \in \Gamma^*\)

Using the stack, a PDA can:

• Push symbols onto the stack (replace top \(A\) with \(BA\), so \(B\) is now on top)
• Pop the top symbol (replace top \(A\) with \(\varepsilon\), i.e., nothing)
• Leave the stack unchanged (replace top \(A\) with \(A\))
• Make \(\varepsilon\)-moves — transitions that consume no input, only modify the stack

Acceptance criteria: A string is accepted if, after reading it completely, the PDA is in an accepting (final) state. The stack content at the end does not matter for acceptance by final state.

1.4 Formal Definition of a PDA

A Pushdown Automaton is a 7-tuple:

\[P = (Q,\, I,\, \Gamma,\, \delta,\, q_0,\, Z_0,\, F)\]

where:

• \(Q\) — finite set of states
• \(I\) — finite input alphabet (the symbols the PDA reads from its tape)
• \(\Gamma\) — finite stack alphabet (the symbols that can appear on the stack; note \(I\) and \(\Gamma\) may overlap)
• \(\delta: Q \times (I \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)\) — the transition function (a partial function mapping to sets of possible outcomes)
• \(q_0 \in Q\) — the initial state
• \(Z_0 \in \Gamma\) — the initial stack symbol (bottom-of-stack marker, placed on the stack at the start)
• \(F \subseteq Q\) — the set of accepting (final) states

Reading the transition function: A transition \(\delta(q, a, A) \ni (q', \alpha)\) means:

In state \(q\), reading input symbol \(a\) (or \(\varepsilon\)), with stack symbol \(A\) on top: move to state \(q'\) and replace \(A\) with the string \(\alpha\).

The graphical notation on arrows is: \(a,\, A / \alpha\) — meaning “read \(a\) from input, pop \(A\) from stack, push \(\alpha\).”

• To push \(B\) onto the stack below \(A\): write \(A / BA\) (replace \(A\) with \(BA\); now \(B\) is on top)
• To pop \(A\): write \(A / \varepsilon\) (replace \(A\) with nothing)
• To leave the stack unchanged: write \(A / A\)

Conditions on \(Z_0\):

• The stack always contains at least \(Z_0\)
• \(Z_0\) is never removed from the stack
• No additional copies of \(Z_0\) are pushed onto the stack

1.5 Deterministic Pushdown Automata (DPDA)

The general PDA above is nondeterministic: \(\delta(q, a, A)\) can contain multiple pairs, meaning the PDA can “choose” among several transitions at each step. Nondeterministic PDAs (NPDAs) are powerful tools, but in practice, compilers use deterministic PDAs.

A PDA \(M = (Q, I, \Gamma, \delta, q_0, Z_0, F)\) is a Deterministic Pushdown Automaton (DPDA) if it satisfies both of the following conditions:

1. At most one transition at each step: For every \(q \in Q\), every \(x \in I \cup \{\varepsilon\}\), and every \(\gamma \in \Gamma\), the set \(\delta(q, x, \gamma)\) has at most one element.
2. No conflict between input and \(\varepsilon\)-transitions: For every \(q \in Q\), every \(x \in I\), and every \(\gamma \in \Gamma\), the two sets \(\delta(q, x, \gamma)\) and \(\delta(q, \varepsilon, \gamma)\) cannot both be non-empty.

The second condition says: if there is an \(\varepsilon\)-transition from state \(q\) with stack top \(\gamma\), then there must be no input-reading transition from the same state \(q\) with the same stack top \(\gamma\). This prevents the PDA from having to “choose” between reading input or making a spontaneous move.

Why the \(\varepsilon\)-rule matters: If both \(\delta(q, a, A)\) and \(\delta(q, \varepsilon, A)\) were non-empty simultaneously, the PDA would be nondeterministic — it could either consume input symbol \(a\) or make a spontaneous move. DPDAs forbid this ambiguity.

Practical convention: We typically use \(\varepsilon, Z_0 / Z_0\) as the final transition to an accepting state, after all input has been consumed and the stack holds only \(Z_0\).

1.6 Configurations and Transitions

To formally describe the execution of a PDA, we introduce the notion of a configuration.

1.6.1 Configuration

A configuration is a “snapshot” of the PDA at any instant. It captures everything about the current computation:

\[c = (q, x, \gamma)\]

where:

• \(q \in Q\) — the current state of the control device
• \(x \in I^*\) — the unread portion of the input string (the part not yet consumed)
• \(\gamma \in \Gamma^*\) — the current stack contents (entire stack, from top to bottom)

Convention: The stack is written top-first. If \(\gamma = A\beta\), then \(A\) is the top of the stack and \(\beta\) is everything below.

Example: The configuration \(c = (q_1, abbb, ABZ_0)\) means: the PDA is in state \(q_1\), the remaining unread input is \(abbb\), and the stack (top to bottom) contains \(A\), \(B\), \(Z_0\).

Initial configuration: \((q_0, x, Z_0)\) for any input string \(x\).

1.6.2 Transitions Between Configurations

The symbol \(\vdash\) (“yields” or “transitions to”) describes a single step of PDA computation. There are two cases:

Case 1 — Reading an input symbol: If \(\delta(q, a, A) = (q', \alpha)\) is defined, and the current configuration has \(A\) on top of the stack and \(ax\) as remaining input, then:

\[(q,\; ax,\; A\beta) \;\vdash\; (q',\; x,\; \alpha\beta)\]

In words: consume the input symbol \(a\), pop \(A\) from the stack, push \(\alpha\), move to state \(q'\).

Case 2 — \(\varepsilon\)-move (spontaneous): If \(\delta(q, \varepsilon, A) = (q', \alpha)\) is defined, and the current configuration has \(A\) on top of the stack:

\[(q,\; x,\; A\beta) \;\vdash\; (q',\; x,\; \alpha\beta)\]

In words: do NOT consume any input, pop \(A\) from the stack, push \(\alpha\), move to state \(q'\).

The key difference between the two cases: in Case 1, the input head advances by one symbol; in Case 2, the input head stays in place.

1.6.3 Multi-Step Computation: \(\vdash^*\)

We define \(\vdash^*\) as the reflexive transitive closure of \(\vdash\). That is, \(c_1 \vdash^* c_k\) means there is a sequence of zero or more steps:

\[c_1 \vdash c_2 \vdash c_3 \vdash \cdots \vdash c_k\]

The \(\vdash^*\) relation captures the complete computation path from one configuration to another.

1.6.4 Acceptance by a PDA

A string \(x \in I^*\) is accepted by PDA \(M = (Q, I, \Gamma, \delta, q_0, Z_0, F)\) if:

\[(q_0,\; x,\; Z_0) \;\vdash^*\; (q,\; \varepsilon,\; \gamma)\]

for some \(q \in F\) and some \(\gamma \in \Gamma^*\).

In plain English: starting from the initial configuration (state \(q_0\), full input \(x\), stack containing only \(Z_0\)), the PDA can reach a configuration where:

1. The entire input has been consumed (remaining input is \(\varepsilon\))
2. The current state is accepting (\(q \in F\))
3. The stack can contain anything (\(\gamma\) is arbitrary)

The language recognized by \(M\) is:

\[L(M) = \{x \in I^* \mid (q_0, x, Z_0) \vdash^* (q, \varepsilon, \gamma) \text{ for some } q \in F, \gamma \in \Gamma^*\}\]

1.7 Two Acceptance Modes

A PDA can accept a string in two different ways:

• Acceptance by final state: The input is completely consumed and the PDA is in a state \(q \in F\). The stack content is irrelevant.
• Acceptance by empty stack: The input is completely consumed and the stack contains only \(Z_0\) (effectively empty). The state does not matter.

For nondeterministic PDAs, these two acceptance modes are equivalent: any language accepted by one mode can be accepted by the other (using a different PDA). For deterministic PDAs, however, the two modes are not equivalent.

A subtlety about empty-stack acceptance: Languages accepted by empty stack must be prefix-free — no string in the language is a proper prefix of another string in the language. Once the stack empties on reading \(w\), processing any extension \(wz\) is impossible.

1.8 Worked Example: PDA for \(L = \{a^n b^n \mid n \geq 1\}\)

This classic example shows how a PDA uses its stack to count symbols.

Strategy: Push one stack symbol \(A\) for each \(a\) in the input. When \(b\)’s start appearing, pop one \(A\) for each \(b\). If the stack holds only \(Z_0\) exactly when all \(b\)’s are consumed, the counts matched perfectly.

PDA specification:

• States: \(p_0\) (start), \(p_1\) (reading \(a\)’s), \(p_2\) (reading \(b\)’s), \(p_3\) (accepting)
• Stack alphabet: \(\Gamma = \{Z_0, A\}\)
• Transitions:

Transition	Notation	Meaning
\(p_0 \to p_1\)	\(a,\, Z_0 / AZ_0\)	Read first \(a\); push \(A\) on top of \(Z_0\)
\(p_1 \circlearrowleft\)	\(a,\, A / AA\)	Read each subsequent \(a\); push another \(A\)
\(p_1 \to p_2\)	\(b,\, A / \varepsilon\)	Read first \(b\); pop one \(A\)
\(p_2 \circlearrowleft\)	\(b,\, A / \varepsilon\)	Read each subsequent \(b\); pop one \(A\)
\(p_2 \to p_3\)	\(\varepsilon,\, Z_0 / Z_0\)	Input exhausted; \(Z_0\) on top means all \(A\)’s were matched; accept

Trace for input \("aabb"\):

Step	State	Remaining Input	Stack (top first)	Rule Applied
1	\(p_0\)	\(\mathbf{a}abb\)	\(Z_0\)	\(a,\, Z_0 / AZ_0\): push \(A\)
2	\(p_1\)	\(\mathbf{a}bb\)	\(A, Z_0\)	\(a,\, A / AA\): push \(A\)
3	\(p_1\)	\(\mathbf{b}b\)	\(A, A, Z_0\)	\(b,\, A / \varepsilon\): pop \(A\)
4	\(p_2\)	\(\mathbf{b}\)	\(A, Z_0\)	\(b,\, A / \varepsilon\): pop \(A\)
5	\(p_2\)	\(\varepsilon\)	\(Z_0\)	\(\varepsilon,\, Z_0 / Z_0\): accept
6	\(p_3\)	\(\varepsilon\)	\(Z_0\)	ACCEPT \(\checkmark\)

The full computation is: \[(p_0, aabb, Z_0) \vdash (p_1, abb, AZ_0) \vdash (p_1, bb, AAZ_0) \vdash (p_2, b, AZ_0) \vdash (p_2, \varepsilon, Z_0) \vdash (p_3, \varepsilon, Z_0)\]

1.9 More PDA Examples

1.9.1 PDA for \(L_2 = \{a^n b a^n \mid n \in \mathbb{N}^+\}\)

Strategy: Push one \(A\) per \(a\) before the \(b\). The single \(b\) acts as a pivot. After seeing \(b\), pop one \(A\) per \(a\) on the right side. If the stack reaches \(Z_0\) exactly at the end of input, the two \(a\)-blocks are equal.

• States: \(q_0\) (start, push phase), \(q_1\) (pop phase, after \(b\)), \(q_2\) (accepting)
• Transitions:

Transition	Notation	Meaning
\(q_0 \circlearrowleft\)	\(a,\, Z_0 / AZ_0\)	First \(a\) before \(b\): push \(A\)
\(q_0 \circlearrowleft\)	\(a,\, A / AA\)	Each subsequent \(a\) before \(b\): push \(A\)
\(q_0 \to q_1\)	\(b,\, A / A\)	See the \(b\); keep stack unchanged, change state
\(q_1 \circlearrowleft\)	\(a,\, A / \varepsilon\)	Each \(a\) after \(b\): pop one \(A\)
\(q_1 \to q_2\)	\(\varepsilon,\, Z_0 / Z_0\)	All \(A\)’s matched; accept

1.9.2 PDA for \(L_3 = \{vcv^R \mid v \in \{a,b\}^*\}\)

The language \(L_3\) consists of strings of the form \(v \cdot c \cdot v^R\): a string \(v\), a center marker \(c\), then \(v\) reversed. The \(c\) serves as the “middle pivot.”

Strategy: Push all symbols of \(v\) onto the stack. When \(c\) is read, switch to pop mode. For each symbol of \(v^R\), pop the matching symbol from the stack. If the stack reaches \(Z_0\) after all input, accept.

• States: \(q_0\) (push phase), \(q_1\) (pop phase, after \(c\)), \(q_2\) (accepting)
• Key transitions (push phase, state \(q_0\), loops):
  • \(a,\, Z_0 / AZ_0\); \(b,\, Z_0 / BZ_0\); \(a,\, A / AA\); \(a,\, B / AB\); \(b,\, A / BA\); \(b,\, B / BB\)
• Pivot (on seeing \(c\)): \(c,\, A / A\); \(c,\, B / B\); \(c,\, Z_0 / Z_0\) (all move \(q_0 \to q_1\))
• Pop phase (state \(q_1\), loops): \(a,\, A / \varepsilon\); \(b,\, B / \varepsilon\)
• Accept: \(\varepsilon,\, Z_0 / Z_0\) (move \(q_1 \to q_2\))

1.9.3 PDA for Balanced Parentheses

The language of balanced (well-formed) parentheses is the prototypical context-free language. Intuitively, each ( must have a matching ) and matched pairs must be properly nested.

• States: \(q_0\) (start), \(q_1\) (processing), \(q_2\) (accepting)
• Transitions:
  • \(q_0 \to q_1\): \((,\, Z_0 / PZ_0\) — first (: push \(P\)
  • \(q_1 \circlearrowleft\): \((,\, P / PP\) — each additional (: push \(P\)
  • \(q_1 \circlearrowleft\): \(),\, P / \varepsilon\) — each ): pop one \(P\) (matching the ()
  • \(q_1 \to q_2\): \(\varepsilon,\, Z_0 / Z_0\) — input exhausted, stack empty: accept

1.10 PDAs vs FSAs: The Big Picture

• Every regular language can be recognized by a PDA (just simulate the FSA without using the stack).
• PDAs can recognize languages that no FSA can (e.g., \(a^n b^n\)).
• Therefore, the class of context-free languages strictly contains the class of regular languages.

Classic PDA for aⁿbⁿ

• Regular languages \(\subsetneq\) Languages recognized by PDAs (context-free languages)
• Examples of context-free but not regular: \(a^n b^n\), \(vcv^R\), balanced parentheses
• Examples beyond PDAs: \(a^n b^n c^n\) (requires counting three quantities simultaneously — no stack can do this)

Memory perspective:

• FSA: fixed, bounded memory (only the current state — a fixed number of bits)
• PDA: finite but not fixed — the stack can grow without bound (unbounded memory)
• Key insight: regular languages are about bounded memory; context-free languages require unbounded memory (but with a specific LIFO structure)

1.11 PDAs and Compilers

PDAs are directly connected to how modern compilers work. A compiler is a program that translates source code (e.g., C, Python) into another language (e.g., machine code). It operates in several phases:

Regular languages are a proper subset of context-free languages

1. Lexical Analysis (Lexing): Breaks source code into tokens — the smallest meaningful units (keywords, identifiers, operators, etc.). The syntax of tokens is regular, so an FSA (or regular expression engine) performs this phase.
2. Syntax Analysis (Parsing): Verifies that the sequence of tokens conforms to the grammar of the programming language. Programming languages have nested structures (balanced brackets, function calls, arithmetic expressions), which are context-free. A PDA performs this phase.
3. Semantic Analysis: Checks type correctness, scope rules, etc.
4. Code Generation and Optimization: Produces and optimizes the target code.

Why PDAs for parsing? Programming languages have constructs requiring matched/nested structures:

• {...} blocks in C/Java
• begin...end in Pascal
• Parenthesized arithmetic expressions
• Nested function calls

These are precisely the kinds of structures that PDAs can handle and FSAs cannot.

Lexical analysis uses FSAs because tokens (like identifiers, numbers, keywords) follow regular patterns. For example, a Pascal identifier matches the regular pattern <letter>(<letter>|<digit>)*, which is easily recognized by an FSA.

Syntax analysis uses PDAs because grammar rules like “an expression is a term, then an operator, then another expression — possibly parenthesized” are context-free.

“Context-free grammars have played a central role in compiler technology since the 1960s… There is an automaton-like notation, called the ‘pushdown automaton’, that also describes all and only the context-free languages.” — John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman

1.12 The Pumping Lemma for Context-Free Languages (Bar-Hillel Lemma)

Just as the Pumping Lemma for regular languages gives us a tool to prove that certain languages are not regular, there is an analogous tool for context-free languages.

1.12.1 Pumping Lemma for Regular Languages (Recap)

Pumping Lemma (FSA): If \(L \subseteq \Sigma^*\) is a regular language, then there exists \(m \geq 1\) such that any \(w \in L\) with \(|w| \geq m\) can be written as \(w = xyz\) satisfying:

• \(y \neq \varepsilon\) (i.e., \(|y| \geq 1\))
• \(|xy| \leq m\)
• \(xy^i z \in L\) for any \(i \geq 0\)

The contrapositive is the tool for proving non-regularity: if no such decomposition exists for some word in \(L\), then \(L\) is not regular.

1.12.2 Bar-Hillel Lemma (Pumping Lemma for Context-Free Languages)

Bar-Hillel Lemma: If \(L \subseteq I^*\) is a context-free language (recognized by a PDA), then there exists \(m \geq 1\) such that any \(w \in L\) with \(|w| \geq m\) can be written as \(w = x_1 x_2 x_3 x_4 x_5\) satisfying:

• \(|x_2 x_4| > 0\) (at least one of \(x_2\) or \(x_4\) is non-empty)
• \(|x_2 x_3 x_4| \leq m\) (the “middle” portion is not too long)
• \(x_1 x_2^i x_3 x_4^i x_5 \in L\) for any \(i \geq 0\) (pumping both \(x_2\) and \(x_4\) simultaneously keeps the string in \(L\))

Key difference from regular Pumping Lemma: In the regular case, we pump a single segment \(y\). In the context-free case, we pump two segments (\(x_2\) and \(x_4\)) simultaneously — they must be pumped by the same number of repetitions \(i\).

The intuition comes from parse trees (Chomsky normal form). In a sufficiently tall parse tree, some non-terminal \(N\) must repeat. The two “arms” hanging from the two occurrences of \(N\) yield the two pumpable segments \(x_2\) and \(x_4\).

Bar-Hillel intuition: a repeated nonterminal creates two pumpable branches

1.12.3 Contrapositive: Proving Non-Context-Freeness

Bar-Hillel Lemma (Corollary): If for any \(m \geq 1\) there exists \(w \in L\) with \(|w| \geq m\) such that for every decomposition \(w = x_1 x_2 x_3 x_4 x_5\) with \(|x_2 x_4| > 0\) and \(|x_2 x_3 x_4| \leq m\), there exists \(i \geq 0\) with \(x_1 x_2^i x_3 x_4^i x_5 \notin L\), then \(L\) is not context-free (cannot be recognized by any PDA).

The two-player game formulation:

Player 1 (Adversary)	Player 2 (You)
Picks any \(m \geq 1\)	Choose \(w \in L\) with \(|w| \geq m\)
Picks any split \(w = x_1 x_2 x_3 x_4 x_5\) with \(|x_2 x_4| > 0\) and \(|x_2 x_3 x_4| \leq m\)	Find \(i \geq 0\) such that \(x_1 x_2^i x_3 x_4^i x_5 \notin L\)

You win (and \(L\) is not context-free) if you can always find a defeating \(i\).

1.12.4 Classic Example: \(L = \{a^n b^n c^n \mid n \in \mathbb{N}\}\)

Claim: \(L = \{a^n b^n c^n \mid n \geq 0\}\) is not recognized by any PDA.

Proof sketch: Let \(m \geq 1\). Choose \(w = a^m b^m c^m \in L\) (with \(|w| = 3m \geq m\)). For any decomposition \(w = x_1 x_2 x_3 x_4 x_5\) with \(|x_2 x_4| > 0\) and \(|x_2 x_3 x_4| \leq m\):

The distance from the first \(a\) to the last \(c\) is \(3m\), but \(|x_2 x_3 x_4| \leq m\). Therefore \(x_2 x_3 x_4\) cannot span all three symbol types simultaneously — it can contain at most two types of symbols (only \(a\)’s, only \(b\)’s, only \(c\)’s, or \(a\)’s and \(b\)’s, or \(b\)’s and \(c\)’s).

In every case, pumping with \(i = 2\) creates a string where at least one count is wrong:

• If \(x_2 x_4\) contains only \(a\)’s: pumping adds more \(a\)’s but no \(b\)’s or \(c\)’s, giving \(a^{m+k} b^m c^m \notin L\).
• If \(x_2 x_4\) contains only \(b\)’s: pumping gives \(a^m b^{m+k} c^m \notin L\).
• If \(x_2 x_4\) contains only \(c\)’s: pumping gives \(a^m b^m c^{m+k} \notin L\).
• If \(x_2 x_4\) spans \(a\)’s and \(b\)’s: pumping adds \(a\)’s and \(b\)’s but not \(c\)’s, giving an unbalanced string not in \(L\).
• If \(x_2 x_4\) spans \(b\)’s and \(c\)’s: pumping adds \(b\)’s and \(c\)’s but not \(a\)’s, same problem.

In all cases, \(x_1 x_2^2 x_3 x_4^2 x_5 \notin L\). Therefore \(L\) is not context-free. \(\square\)

1.13 Beyond PDAs: The Limits of Context-Free Languages

Not all languages are context-free. The language \(L = \{a^n b^n c^n \mid n \geq 0\}\) is a canonical example of a language that lies beyond the power of PDAs. To recognize it, you would need to count three quantities simultaneously, but a stack can only maintain one linear count at a time.

To recognize such languages, we need an even more powerful model: the Turing Machine, which has a full read/write tape (not just a stack). The stack is a destructive memory — once a symbol is popped, it is gone. A tape is persistent — reading does not destroy.

The hierarchy of languages mirrors the hierarchy of machines:

• Regular languages — recognized by FSAs
• Context-free languages — recognized by PDAs (stack memory)
• Context-sensitive and more — recognized by Turing Machines (tape memory)

---

2. Definitions

• Pushdown Automaton (PDA): A computational model consisting of a finite control unit, an input tape, and an unbounded stack. Formally a 7-tuple \((Q, I, \Gamma, \delta, q_0, Z_0, F)\). PDAs recognize exactly the class of context-free languages.
• Deterministic Pushdown Automaton (DPDA): A PDA where (1) \(|\delta(q, x, \gamma)| \leq 1\) for all \(q, x, \gamma\) (at most one transition at each step), and (2) \(\delta(q, x, \gamma) \neq \emptyset\) implies \(\delta(q, \varepsilon, \gamma) = \emptyset\) for all \(x \in I\) (no conflict between input-reading and \(\varepsilon\)-transitions).
• Nondeterministic PDA: A PDA where \(\delta(q, a, A)\) may contain multiple possible transitions. The PDA accepts if some sequence of choices leads to acceptance.
• Stack: A last-in, first-out (LIFO) data structure used by a PDA as its main memory. Supports two operations: push (add to top) and pop (remove from top).
• Stack Alphabet (\(\Gamma\)): The finite set of symbols that may appear on the PDA’s stack. Typically includes the bottom-of-stack marker \(Z_0\).
• Bottom-of-Stack Symbol (\(Z_0\)): A special symbol placed at the bottom of the PDA’s stack initially. It is never removed and never duplicated. When \(Z_0\) is on top, the stack is effectively empty.
• Input Alphabet (\(I\)): The finite set of symbols that the PDA reads from its input tape. Distinct from \(\Gamma\) conceptually, though they may share symbols.
• Transition Function (\(\delta\)): The function \(\delta: Q \times (I \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)\) specifying PDA moves. A transition \((q', \alpha) \in \delta(q, a, A)\) means: in state \(q\), reading \(a\) (or \(\varepsilon\)) from input and \(A\) from the stack top, move to state \(q'\) and replace \(A\) with string \(\alpha\).
• \(\varepsilon\)-move: A PDA transition of the form \(\delta(q, \varepsilon, A) = (q', \alpha)\) that does not consume any input symbol. The PDA changes state and modifies the stack “spontaneously,” without reading the next character.
• \(\varepsilon\)-rule (DPDA condition): If there is an \(\varepsilon\)-transition from state \(q\) with stack top \(Z\), then there must be no input-reading transition from the same state \(q\) with the same stack top \(Z\). This ensures determinism.
• Configuration: A triple \((q, x, \gamma)\) representing a complete “snapshot” of a PDA: current state \(q\), unread input \(x\), and stack contents \(\gamma\) (top to bottom). Also called a “PDA instantaneous description.”
• Transition Between Configurations (\(\vdash\)): A single computation step. \((q, ax, A\beta) \vdash (q', x, \alpha\beta)\) if \(\delta(q, a, A) = (q', \alpha)\); or \((q, x, A\beta) \vdash (q', x, \alpha\beta)\) if \(\delta(q, \varepsilon, A) = (q', \alpha)\).
• Reflexive Transitive Closure (\(\vdash^*\)): \(c_1 \vdash^* c_k\) means there is a sequence of zero or more steps from configuration \(c_1\) to \(c_k\).
• Acceptance by Final State: A string \(x\) is accepted if \((q_0, x, Z_0) \vdash^* (q, \varepsilon, \gamma)\) for some \(q \in F\) and \(\gamma \in \Gamma^*\). The stack content at the end is irrelevant.
• Acceptance by Empty Stack: A string \(x\) is accepted if \((q_0, x, Z_0) \vdash^* (q, \varepsilon, Z_0)\) for some state \(q\) (not necessarily in \(F\)). For DPDAs, these two acceptance modes are not equivalent.
• Context-Free Language (CFL): A language recognized by a pushdown automaton, or equivalently, generated by a context-free grammar. Every regular language is context-free, but not vice versa.
• Pumping Lemma (Regular Languages): If \(L\) is regular, there exists \(m \geq 1\) such that every \(w \in L\) with \(|w| \geq m\) has a split \(w = xyz\) with \(|y| \geq 1\), \(|xy| \leq m\), and \(xy^i z \in L\) for all \(i \geq 0\).
• Bar-Hillel Lemma (Pumping Lemma for CFLs): If \(L\) is a context-free language, there exists \(m \geq 1\) such that every \(w \in L\) with \(|w| \geq m\) has a split \(w = x_1 x_2 x_3 x_4 x_5\) with \(|x_2 x_4| > 0\), \(|x_2 x_3 x_4| \leq m\), and \(x_1 x_2^i x_3 x_4^i x_5 \in L\) for all \(i \geq 0\).
• Compiler: A program that translates source code in one language (e.g., C) into another language (e.g., machine code), typically via multiple phases: lexical analysis, syntax analysis, semantic analysis, and code generation.
• Lexical Analysis (Lexing): The first phase of compilation; breaks source code into tokens (keywords, identifiers, operators). Uses FSAs (regular languages) to recognize token patterns.
• Syntax Analysis (Parsing): The second phase of compilation; checks that the sequence of tokens conforms to the language grammar and constructs a parse tree. Uses PDAs (context-free languages) to handle nested language structures.
• Token: The smallest meaningful unit in a programming language (e.g., an identifier sum, an operator +, a keyword if). Recognized by lexical analysis.
• Parse Tree (Syntax Tree): A tree structure built during syntax analysis that represents the grammatical structure of the source code. Leaf nodes are tokens; internal nodes are grammar rules.
• Abstract Syntax Tree (AST): A simplified parse tree that represents the logical structure of the source code, used in semantic analysis, optimization, and code generation.
• Prefix-Free Language: A language \(L\) where no string in \(L\) is a proper prefix of another string in \(L\). Languages accepted by a DPDA via empty stack must be prefix-free.

---

3. Formulas

• PDA formal definition: \(P = (Q, I, \Gamma, \delta, q_0, Z_0, F)\) where \(\delta: Q \times (I \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma^*)\)
• Transition notation: \(a,\, A / \alpha\) — read \(a\) from input (or \(\varepsilon\) for spontaneous), pop \(A\) from stack, push \(\alpha\)
• Push \(B\) onto stack: replace top \(A\) with \(BA\) — write \(A / BA\)
• Pop top \(A\): replace top \(A\) with \(\varepsilon\) — write \(A / \varepsilon\)
• Leave stack unchanged: replace top \(A\) with \(A\) — write \(A / A\)
• DPDA condition 1: \(|\delta(q, x, \gamma)| \leq 1\) for all \(q \in Q\), \(x \in I \cup \{\varepsilon\}\), \(\gamma \in \Gamma\)
• DPDA condition 2: \(\delta(q, x, \gamma) \neq \emptyset \Rightarrow \delta(q, \varepsilon, \gamma) = \emptyset\) for all \(q \in Q\), \(x \in I\), \(\gamma \in \Gamma\)
• Configuration: \((q, x, \gamma)\) where \(q \in Q\), \(x \in I^*\) (remaining input), \(\gamma \in \Gamma^*\) (stack, top first)
• Transition (input symbol): \((q, ax, A\beta) \vdash (q', x, \alpha\beta)\) when \(\delta(q, a, A) = (q', \alpha)\)
• Transition (\(\varepsilon\)-move): \((q, x, A\beta) \vdash (q', x, \alpha\beta)\) when \(\delta(q, \varepsilon, A) = (q', \alpha)\)
• Acceptance by final state: \(x \in L(M) \iff (q_0, x, Z_0) \vdash^* (q, \varepsilon, \gamma)\) for some \(q \in F\), \(\gamma \in \Gamma^*\)
• Language recognized: \(L(M) = \{x \in I^* \mid (q_0, x, Z_0) \vdash^* (q, \varepsilon, \gamma),\; q \in F,\; \gamma \in \Gamma^*\}\)
• Pumping Lemma (regular): \(L\) regular \(\Rightarrow\) \(\exists m \geq 1\) s.t. \(\forall w \in L\) with \(|w| \geq m\), \(\exists\) split \(w = xyz\), \(|y| \geq 1\), \(|xy| \leq m\), \(\forall i \geq 0: xy^i z \in L\)
• Bar-Hillel Lemma (CFL): \(L\) context-free \(\Rightarrow\) \(\exists m \geq 1\) s.t. \(\forall w \in L\) with \(|w| \geq m\), \(\exists\) split \(w = x_1x_2x_3x_4x_5\), \(|x_2x_4| > 0\), \(|x_2x_3x_4| \leq m\), \(\forall i \geq 0: x_1x_2^ix_3x_4^ix_5 \in L\)
• Contrapositive (Bar-Hillel): \(L\) is not CFL if \(\forall m \geq 1\), \(\exists w \in L\) with \(|w| \geq m\) such that \(\forall\) splits \(x_1x_2x_3x_4x_5 = w\) with \(|x_2x_4| > 0\) and \(|x_2x_3x_4| \leq m\): \(\exists i \geq 0\) with \(x_1x_2^ix_3x_4^ix_5 \notin L\)

---

4. Examples

4.1. Construct a DPDA for \(L = \{a^n b^{2n} \mid n \geq 1\}\) (Lab 6, Task 1)

Build a DPDA that recognizes the language \(L = \{a^n b^{2n} \mid n \geq 1\}\) — strings of \(n\) \(a\)’s followed by exactly \(2n\) \(b\)’s.

Click to see the solution

Key Concept: For each \(a\) read, push two stack symbols (so you accumulate \(2n\) stack symbols for \(n\) \(a\)’s). Then pop one stack symbol per \(b\). When all \(b\)’s are consumed and the stack holds only \(Z_0\), the ratio \(1:2\) is satisfied.

DPDA for aⁿb²ⁿ

1. PDA specification:

   • States: \(q_0\) (start), \(q_1\) (reading \(a\)’s), \(q_2\) (reading \(b\)’s), \(q_3\) (accepting)
   • Stack alphabet: \(\Gamma = \{Z_0, A\}\)

2. Transitions:

   Transition	Notation	Meaning
   \(q_0 \to q_1\)	\(a,\, Z_0 / AAZ_0\)	First \(a\): push two \(A\)’s
   \(q_1 \circlearrowleft\)	\(a,\, A / AAA\)	Each subsequent \(a\): push two more \(A\)’s (net: replace top \(A\) with \(AAA\), adding two)
   \(q_1 \to q_2\)	\(b,\, A / \varepsilon\)	First \(b\): pop one \(A\)
   \(q_2 \circlearrowleft\)	\(b,\, A / \varepsilon\)	Each subsequent \(b\): pop one \(A\)
   \(q_2 \to q_3\)	\(\varepsilon,\, Z_0 / Z_0\)	All \(A\)’s consumed; accept

   Note on the push step: When reading \(a\) with \(A\) on top, we replace \(A\) with \(AAA\) — effectively, we keep the existing \(A\) and add two more on top, so the stack grows by two per \(a\). Equivalently, since each \(a\) should add two symbols: we replace \(A \to AAA\) (adding two) which matches the \(2:1\) ratio.

3. Trace for input \("abb"\) (\(n=1\), \(2n=2\)):

   • \(q_0 \xrightarrow{a,\,Z_0/AAZ_0} q_1\): stack = \(A, A, Z_0\)
   • \(q_1 \xrightarrow{b,\,A/\varepsilon} q_2\): stack = \(A, Z_0\)
   • \(q_2 \xrightarrow{b,\,A/\varepsilon} q_2\): stack = \(Z_0\)
   • \(q_2 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_3\): ACCEPT \(\checkmark\)

4. Trace for input \("aabbbb"\) (\(n=2\), \(2n=4\)):

   • \(q_0 \xrightarrow{a,\,Z_0/AAZ_0} q_1\): stack = \(A,A,Z_0\)
   • \(q_1 \xrightarrow{a,\,A/AAA} q_1\): stack = \(A,A,A,Z_0\) (net +2: \(A \to AAA\) adds two)
   • \(q_1 \xrightarrow{b,\,A/\varepsilon} q_2\): stack = \(A,A,Z_0\)
   • \(q_2 \xrightarrow{b,\,A/\varepsilon} q_2\): stack = \(A,Z_0\)
   • \(q_2 \xrightarrow{b,\,A/\varepsilon} q_2\): stack = \(Z_0\)
   • \(q_2 \xrightarrow{b,\,A/\varepsilon} q_2\): stack = — (ERROR: stack underflow — wrong, recheck)

   Correction: Let’s recount. For \(n=2\): push 2 for first \(a\) (stack = \(AA Z_0\)), then replace top \(A\) with \(AAA\) for second \(a\): stack = \(A,A,A,Z_0\) (4 \(A\)’s? No — \(AA Z_0\) with top \(A\) replaced by \(AAA\) gives \(A,A,A,Z_0\) — that’s 3 \(A\)’s + \(Z_0\)). We need \(2 \cdot 2 = 4\) symbols for \(n=2\).

   Revised approach: A cleaner strategy: for each \(a\), push two \(A\)’s unconditionally. Use a separate state to push the second \(A\).

   Transition	Notation	Meaning
   \(q_0 \to q_1\)	\(a,\, Z_0 / AZ_0\)	First \(a\): push first \(A\)
   \(q_1 \to q_2\)	\(\varepsilon,\, A / AA\)	Spontaneous: push second \(A\)
   \(q_2 \to q_2\)	\(a,\, A / AA\)	Subsequent \(a\) (first push)
   …	…	…

   Simplest correct approach: For each \(a\), push two \(A\)’s by using a helper state:

   • States: \(q_0\) (start), \(q_1\) (just read \(a\), need to push second \(A\)), \(q_2\) (ready to read \(a\) or \(b\)), \(q_3\) (reading \(b\)’s), \(q_4\) (accepting)

   Transition	Notation	Meaning
   \(q_0 \to q_1\)	\(a,\, Z_0 / AZ_0\)	First \(a\): push one \(A\)
   \(q_1 \to q_2\)	\(\varepsilon,\, A / AA\)	Push second \(A\) (spontaneous)
   \(q_2 \to q_1\)	\(a,\, A / AA\)	Another \(a\): push first of two \(A\)’s
   \(q_2 \to q_3\)	\(b,\, A / \varepsilon\)	Start reading \(b\)’s: pop one \(A\)
   \(q_3 \circlearrowleft\)	\(b,\, A / \varepsilon\)	Each \(b\): pop one \(A\)
   \(q_3 \to q_4\)	\(\varepsilon,\, Z_0 / Z_0\)	Stack empty: accept

Answer: The DPDA using a helper state to push two \(A\)’s per \(a\), then popping one \(A\) per \(b\), recognizes \(L = \{a^n b^{2n} \mid n \geq 1\}\).

4.2. Construct a DPDA for Arithmetic Expression Parentheses (Lab 6, Homework 1)

Construct a DPDA that recognizes the language of well-formed parentheses of arithmetic expressions (binary operations). The alphabet is \(I = \{a, (, ), +\}\), where \(a\) represents terms and \(+\) is the binary operator.

Examples in the language: (a + a), ((a) + (a + a)), ((a + a)) The language consists of syntactically valid arithmetic expressions with parenthesized subexpressions.

Click to see the solution

Key Concept: This problem is about recognizing a simple expression grammar. The core constraint is that parentheses must be balanced: each ( must have a matching ), properly nested. The \(a\) and \(+\) symbols are essentially “filler” that don’t affect balancing.

DPDA skeleton for balanced parentheses in arithmetic expressions

Simplification: For the purpose of DPDA construction, the key property is that the parentheses must be balanced. The \(a\) and \(+\) symbols just need to appear in valid positions within the grammar. We model this by tracking open parentheses on the stack.

Grammar (informally):

• An expression is: a term, or ( expression ), or expression + expression

For a simple DPDA approach tracking only parenthesis balance:

1. States: \(q_0\) (processing), \(q_1\) (accepting)

   • Stack alphabet: \(\Gamma = \{Z_0, P\}\) where \(P\) marks an open (

2. Transitions (loops on \(q_0\)):

   Notation	Meaning
   \((,\, Z_0 / PZ_0\)	Open (: push \(P\) (stack was empty)
   \((,\, P / PP\)	Open ( inside another: push \(P\)
   \(),\, P / \varepsilon\)	Close ): pop matching \(P\)
   \(a,\, Z_0 / Z_0\)	Read term \(a\): no stack change
   \(a,\, P / P\)	Read term \(a\) inside parentheses: no stack change
   \(+,\, Z_0 / Z_0\)	Read operator outside parentheses: no stack change
   \(+,\, P / P\)	Read operator inside parentheses: no stack change

3. Accept: \(q_0 \to q_1\): \(\varepsilon,\, Z_0 / Z_0\) — balanced.

4. Trace for \("(a+a)"\):

   • \(q_0 \xrightarrow{(,\,Z_0/PZ_0} q_0\): stack = \(P, Z_0\)
   • \(q_0 \xrightarrow{a,\,P/P} q_0\): stack = \(P, Z_0\)
   • \(q_0 \xrightarrow{+,\,P/P} q_0\): stack = \(P, Z_0\)
   • \(q_0 \xrightarrow{a,\,P/P} q_0\): stack = \(P, Z_0\)
   • \(q_0 \xrightarrow{),\,P/\varepsilon} q_0\): stack = \(Z_0\)
   • \(q_0 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_1\): ACCEPT \(\checkmark\)

Answer: The DPDA tracks parenthesis balance via the stack, accepting when all parentheses are matched and the input is fully consumed.

4.3. Construct a DPDA for \(P = \{xycy^Rx^R \mid x \in \{a,b\}^*, y \in \{d,e\}^*, |x|>0\}\) (Lab 6, Task 2)

Build a DPDA that recognizes \(P = \{xycy^Rx^R \mid x \in \{a,b\}^*, y \in \{d,e\}^*, |x|>0\}\) over the alphabet \(I = \{a,b,c,d,e\}\).

(The string consists of a non-empty string \(x\) over \(\{a,b\}\), followed by a string \(y\) over \(\{d,e\}\), followed by the center marker \(c\), followed by \(y^R\), followed by \(x^R\).)

Click to see the solution

Key Concept: Push all symbols of \(x\) (using stack symbols \(A\) for \(a\), \(B\) for \(b\)) and then all symbols of \(y\) (using \(D\) for \(d\), \(E\) for \(e\)). When \(c\) appears, switch to pop mode: first pop \(y^R\) (matching \(y\) reversed), then pop \(x^R\) (matching \(x\) reversed).

1. PDA specification:
   • States: \(q_0\) (pushing \(x\)), \(q_1\) (pushing \(y\)), \(q_2\) (popping \(y^R\)), \(q_3\) (popping \(x^R\)), \(q_4\) (accepting)
   • Stack alphabet: \(\Gamma = \{Z_0, A, B, D, E\}\)
2. Phase 1 — Push \(x\) (state \(q_0\), loops):
   • \(a,\, Z_0 / AZ_0\); \(b,\, Z_0 / BZ_0\)
   • \(a,\, A / AA\); \(a,\, B / AB\)
   • \(b,\, A / BA\); \(b,\, B / BB\)
3. Transition to \(y\)-push phase (state \(q_0 \to q_1\)): On reading the first \(d\) or \(e\) symbol, switch to \(q_1\):
   • \(d,\, A / DA\); \(d,\, B / DB\); \(e,\, A / EA\); \(e,\, B / EB\)
4. Phase 2 — Push \(y\) (state \(q_1\), loops):
   • \(d,\, D / DD\); \(d,\, E / DE\)
   • \(e,\, D / ED\); \(e,\, E / EE\)
5. Pivot on \(c\) (\(q_1 \to q_2\) or \(q_0 \to q_2\) if \(y\) empty):
   • \(c,\, D / D\); \(c,\, E / E\) (top is a \(y\)-symbol: switch to pop-\(y\) phase)
   • \(c,\, A / A\); \(c,\, B / B\) (no \(y\) was pushed, skip to pop-\(x\) phase: \(q_1 \to q_3\))
6. Phase 3 — Pop \(y^R\) (state \(q_2\), loops):
   • \(d,\, D / \varepsilon\); \(e,\, E / \varepsilon\) (match \(d \leftrightarrow D\), \(e \leftrightarrow E\))
   • Transition to pop-\(x\) phase when hitting an \(x\)-symbol: \(q_2 \to q_3\) on \(\varepsilon\) when top is \(A\) or \(B\): \(\varepsilon,\, A / A\); \(\varepsilon,\, B / B\)
7. Phase 4 — Pop \(x^R\) (state \(q_3\), loops):
   • \(a,\, A / \varepsilon\); \(b,\, B / \varepsilon\) (match \(a \leftrightarrow A\), \(b \leftrightarrow B\))
8. Accept: \(q_3 \to q_4\): \(\varepsilon,\, Z_0 / Z_0\)

Answer: The DPDA with phases for pushing \(x\), pushing \(y\), popping \(y^R\), and popping \(x^R\) (with \(c\) as the pivot) recognizes \(P = \{xycy^Rx^R \mid x \in \{a,b\}^*, y \in \{d,e\}^*, |x|>0\}\).

4.4. Construct a DPDA for Balanced Brackets and Parentheses (Lab 6, Task 3)

Build a DPDA that recognizes the language of nested and balanced brackets and parentheses over the alphabet \(I = \{(, ), [, ]\}\).

Examples of strings in the language: (([])())(), (())[] Examples NOT in the language: ([(]))()(), ([)]

Click to see the solution

Key Concept: Use the stack to track open delimiters. When ( is seen, push a marker \(P\) for parenthesis. When [ is seen, push a marker \(Q\) for bracket. When ) is seen, pop the top and check it is \(P\) (matching parenthesis). When ] is seen, pop and check it is \(Q\) (matching bracket). Accept when the input is exhausted and the stack holds only \(Z_0\).

DPDA for balanced parentheses and brackets

Note: A key challenge is that ([)] must be rejected — the closing symbols must match the most recently opened one. The stack’s LIFO property enforces this naturally.

1. PDA specification:

   • States: \(q_0\) (start, processing), \(q_1\) (accepting)
   • Stack alphabet: \(\Gamma = \{Z_0, P, Q\}\) where \(P\) marks ( and \(Q\) marks [

2. Transitions (all loops on \(q_0\) except the final accept):

   Notation	Meaning
   \((,\, Z_0 / PZ_0\)	Open ( on empty stack: push \(P\)
   \((,\, P / PP\)	Open ( with \(P\) on top: push \(P\)
   \((,\, Q / PQ\)	Open ( with \(Q\) on top: push \(P\)
   \([,\, Z_0 / QZ_0\)	Open [ on empty stack: push \(Q\)
   \([,\, P / QP\)	Open [ with \(P\) on top: push \(Q\)
   \([,\, Q / QQ\)	Open [ with \(Q\) on top: push \(Q\)
   \(),\, P / \varepsilon\)	Close ) with \(P\) on top: pop (matched!)
   \(],\, Q / \varepsilon\)	Close ] with \(Q\) on top: pop (matched!)

3. Accept: \(q_0 \to q_1\): \(\varepsilon,\, Z_0 / Z_0\) — all matched, stack has only \(Z_0\).

4. Rejection (implicitly): If ) is read but \(Q\) (not \(P\)) is on top, there is no defined transition, so the PDA gets stuck and rejects. This correctly rejects strings like ([)].

5. Trace for input \("([])"\):

   • \(q_0 \xrightarrow{(,\,Z_0/PZ_0} q_0\): stack = \(P, Z_0\)
   • \(q_0 \xrightarrow{[,\,P/QP} q_0\): stack = \(Q, P, Z_0\)
   • \(q_0 \xrightarrow{],\,Q/\varepsilon} q_0\): stack = \(P, Z_0\)
   • \(q_0 \xrightarrow{),\,P/\varepsilon} q_0\): stack = \(Z_0\)
   • \(q_0 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_1\): ACCEPT \(\checkmark\)

Answer: The DPDA above recognizes the language of nested and balanced brackets and parentheses over \(\{(, ), [, ]\}\).

4.5. Construct a DPDA for \(L_1 = \{w \in \{a,b\}^* \mid \phi(w,a) = \phi(w,b)\}\) (Lab 6, Task 4)

Build a DPDA that recognizes \(L_1 = \{w \in \{a,b\}^* \mid \phi(w,a) = \phi(w,b)\}\), where \(\phi(s,c)\) is the number of occurrences of character \(c\) in string \(s\). In other words, \(L_1\) is the set of all strings over \(\{a,b\}\) with equal numbers of \(a\)’s and \(b\)’s (in any order).

Click to see the solution

Key Concept: Unlike \(a^n b^n\) where all \(a\)’s come first, here \(a\)’s and \(b\)’s can be interleaved in any order. We use the stack as a counter: push \(A\) for each \(a\) seen (when stack contains only \(Z_0\) or \(A\)’s), and push \(B\) for each \(b\) seen (when stack contains only \(Z_0\) or \(B\)’s). When the top symbol and the input symbol cancel (an \(a\) arrives while the top is \(B\), or a \(b\) arrives while the top is \(A\)), pop the top instead. This is a net balance counter.

1. PDA specification:

   • States: \(q_0\) (processing), \(q_1\) (accepting)
   • Stack alphabet: \(\Gamma = \{Z_0, A, B\}\)
   • \(A\) on the stack means “more \(a\)’s seen so far”; \(B\) means “more \(b\)’s seen so far”

2. Transitions (all loops on \(q_0\)):

   Notation	Meaning
   \(a,\, Z_0 / AZ_0\)	Read \(a\), stack balanced so far: push \(A\) (now +1 \(a\))
   \(a,\, A / AA\)	Read \(a\), currently have excess \(a\)’s: push more \(A\)
   \(a,\, B / \varepsilon\)	Read \(a\), currently have excess \(b\)’s: cancel one \(B\)
   \(b,\, Z_0 / BZ_0\)	Read \(b\), stack balanced so far: push \(B\) (now +1 \(b\))
   \(b,\, B / BB\)	Read \(b\), currently have excess \(b\)’s: push more \(B\)
   \(b,\, A / \varepsilon\)	Read \(b\), currently have excess \(a\)’s: cancel one \(A\)

3. Accept: \(q_0 \to q_1\): \(\varepsilon,\, Z_0 / Z_0\) — all cancelled out, stack holds \(Z_0\): counts equal; accept.

4. Trace for input \("abba"\):

   • \(q_0 \xrightarrow{a,\,Z_0/AZ_0} q_0\): stack = \(A, Z_0\) (1 excess \(a\))
   • \(q_0 \xrightarrow{b,\,A/\varepsilon} q_0\): stack = \(Z_0\) (cancelled)
   • \(q_0 \xrightarrow{b,\,Z_0/BZ_0} q_0\): stack = \(B, Z_0\) (1 excess \(b\))
   • \(q_0 \xrightarrow{a,\,B/\varepsilon} q_0\): stack = \(Z_0\) (cancelled)
   • \(q_0 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_1\): ACCEPT \(\checkmark\)

5. Trace for input \("aab"\) (should reject since \(\phi(w,a)=2 \neq 1=\phi(w,b)\)):

   • \(q_0 \xrightarrow{a,\,Z_0/AZ_0} q_0\): stack = \(A, Z_0\)
   • \(q_0 \xrightarrow{a,\,A/AA} q_0\): stack = \(A, A, Z_0\)
   • \(q_0 \xrightarrow{b,\,A/\varepsilon} q_0\): stack = \(A, Z_0\)
   • Input exhausted; stack is \(A, Z_0\) (not just \(Z_0\)); no \(\varepsilon\)-accept transition applies. REJECT \(\checkmark\)

Answer: The DPDA above uses the stack as a signed counter to recognize \(L_1 = \{w \mid \phi(w,a) = \phi(w,b)\}\).

4.6. Construct a DPDA for \(L_2 = \{a^n b^m a^m b^n \mid n > 0, m > 0\}\) (Lab 6, Task 5)

Build a DPDA that recognizes \(L_2 = \{a^n b^m a^m b^n \mid n > 0, m > 0\}\).

Click to see the solution

Key Concept: The string has the form \(a^n b^m a^m b^n\) — an outer \(a\)-layer, an inner \(b\)-layer, a matching inner \(a\)-layer, and a matching outer \(b\)-layer. Use the stack in two phases:

DPDA for aⁿbᵐaᵐbⁿ

• Phase 1 (outer \(a\)’s): Push \(n\) copies of \(A\) for the \(n\) leading \(a\)’s.
• Phase 2 (inner \(b\)’s): Push \(m\) copies of \(B\) for the \(m\) leading \(b\)’s (on top of the \(A\)’s).
• Phase 3 (inner \(a\)’s): Pop one \(B\) per \(a\) (matching the inner \(b\)’s with inner \(a\)’s).
• Phase 4 (outer \(b\)’s): Pop one \(A\) per \(b\) (matching the outer \(a\)’s with outer \(b\)’s).

1. States: \(q_0\) (reading outer \(a\)’s), \(q_1\) (reading inner \(b\)’s), \(q_2\) (reading inner \(a\)’s), \(q_3\) (reading outer \(b\)’s), \(q_4\) (accepting)

2. Transitions:

   Transition	Notation	Meaning
   \(q_0 \circlearrowleft\)	\(a,\, Z_0 / AZ_0\)	First outer \(a\): push \(A\)
   \(q_0 \circlearrowleft\)	\(a,\, A / AA\)	More outer \(a\)’s: push \(A\)
   \(q_0 \to q_1\)	\(b,\, A / BA\)	First inner \(b\): push \(B\) on top of \(A\)’s
   \(q_1 \circlearrowleft\)	\(b,\, B / BB\)	More inner \(b\)’s: push \(B\)
   \(q_1 \to q_2\)	\(a,\, B / \varepsilon\)	First inner \(a\): pop one \(B\)
   \(q_2 \circlearrowleft\)	\(a,\, B / \varepsilon\)	More inner \(a\)’s: pop \(B\)
   \(q_2 \to q_3\)	\(b,\, A / \varepsilon\)	First outer \(b\): pop one \(A\) (all \(B\)’s gone)
   \(q_3 \circlearrowleft\)	\(b,\, A / \varepsilon\)	More outer \(b\)’s: pop \(A\)
   \(q_3 \to q_4\)	\(\varepsilon,\, Z_0 / Z_0\)	All matched: accept

3. Trace for input \("abba"\) is too short (minimum: \(a^1b^1a^1b^1 = "abab"\)):

   Trace for \("abab"\) (\(n=m=1\)):

   • \(q_0 \xrightarrow{a,\,Z_0/AZ_0} q_0\): stack = \(A, Z_0\)
   • \(q_0 \xrightarrow{b,\,A/BA} q_1\): stack = \(B, A, Z_0\)
   • \(q_1 \xrightarrow{a,\,B/\varepsilon} q_2\): stack = \(A, Z_0\)
   • \(q_2 \xrightarrow{b,\,A/\varepsilon} q_3\): stack = \(Z_0\)
   • \(q_3 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_4\): ACCEPT \(\checkmark\)

Answer: The DPDA with phases for outer \(a\)’s, inner \(b\)’s, inner \(a\)’s, and outer \(b\)’s recognizes \(L_2 = \{a^n b^m a^m b^n \mid n > 0, m > 0\}\).

4.7. Prove That \(L = \{a^n b^n c^n \mid n \in \mathbb{N}\}\) Is Not Context-Free (Tutorial 6, Example 1)

Use the Bar-Hillel Lemma (Pumping Lemma for context-free languages) to prove that \(L = \{a^n b^n c^n \mid n \geq 0\}\) is not a context-free language.

Click to see the solution

Key Concept: In \(L\), the number of \(a\)’s, \(b\)’s, and \(c\)’s must all be equal. The Bar-Hillel Lemma pumps two segments simultaneously, but any two-segment window of size \(\leq m\) in \(a^m b^m c^m\) can cover at most two types of symbols. Pumping creates an imbalance in at least one count.

1. Assume for contradiction that \(L\) is context-free. Let \(m \geq 1\) be the pumping length given by the Bar-Hillel Lemma.

2. Choose the word \(w = a^m b^m c^m \in L\). Note \(|w| = 3m \geq m\).

3. Consider any split \(w = x_1 x_2 x_3 x_4 x_5\) with \(|x_2 x_4| > 0\) and \(|x_2 x_3 x_4| \leq m\).

4. Restrict where \(x_2 x_3 x_4\) can lie: The distance from the first \(a\) to the last \(c\) is \(3m - 1\) characters. Since \(|x_2 x_3 x_4| \leq m < 3m\), the window \(x_2 x_3 x_4\) cannot span all three types of symbols simultaneously. It can cover:

   • Only \(a\)’s, or only \(b\)’s, or only \(c\)’s, or
   • \(a\)’s and \(b\)’s (but not \(c\)’s), or \(b\)’s and \(c\)’s (but not \(a\)’s)

5. Pump with \(i = 2\) (pump up): Consider \(x_1 x_2^2 x_3 x_4^2 x_5\). In every case:

   • If \(x_2 x_4\) contains only \(a\)’s: pumping adds \(a\)’s but no \(b\)’s or \(c\)’s. The result has more \(a\)’s than \(b\)’s and \(c\)’s. \(\notin L\).
   • If \(x_2 x_4\) contains only \(b\)’s: pumping adds \(b\)’s but no \(a\)’s or \(c\)’s. \(\notin L\).
   • If \(x_2 x_4\) contains only \(c\)’s: pumping adds \(c\)’s but no \(a\)’s or \(b\)’s. \(\notin L\).
   • If \(x_2 x_4\) spans \(a\)’s and \(b\)’s: pumping adds more \(a\)’s and \(b\)’s but no extra \(c\)’s. \(\notin L\).
   • If \(x_2 x_4\) spans \(b\)’s and \(c\)’s: pumping adds more \(b\)’s and \(c\)’s but no extra \(a\)’s. \(\notin L\).

6. Conclusion: In every case, \(x_1 x_2^2 x_3 x_4^2 x_5 \notin L\). The Bar-Hillel Lemma is violated. Therefore \(L\) is not context-free. \(\square\)

Answer: \(L = \{a^n b^n c^n \mid n \geq 0\}\) is not a context-free language.

4.8. Construct a DPDA for \(L_1 = \{a^n b^n \mid n \geq 1\}\) (Tutorial 6, Example 2)

Construct a Deterministic Pushdown Automaton (DPDA) that recognizes \(L_1 = \{a^n b^n \mid n \geq 1\}\), and trace the computation on the input \("aabb"\).

Click to see the solution

Key Concept: Use the stack to count \(a\)’s: push one \(A\) per \(a\) read, then pop one \(A\) per \(b\) read. If the stack holds only \(Z_0\) exactly when all \(b\)’s are consumed, the counts matched.

DPDA trace machine for aⁿbⁿ

1. PDA specification:

   • States: \(p_0\) (start), \(p_1\) (reading \(a\)’s), \(p_2\) (reading \(b\)’s), \(p_3\) (accepting)
   • Stack alphabet: \(\Gamma = \{Z_0, A\}\)
   • Input alphabet: \(I = \{a, b\}\)

2. Transitions:

   Transition	Notation	Meaning
   \(p_0 \to p_1\)	\(a,\, Z_0 / AZ_0\)	Read first \(a\); push \(A\) on top of \(Z_0\)
   \(p_1 \circlearrowleft\)	\(a,\, A / AA\)	Read additional \(a\)’s; push \(A\) each time
   \(p_1 \to p_2\)	\(b,\, A / \varepsilon\)	Read first \(b\); pop one \(A\)
   \(p_2 \circlearrowleft\)	\(b,\, A / \varepsilon\)	Read additional \(b\)’s; pop one \(A\) each time
   \(p_2 \to p_3\)	\(\varepsilon,\, Z_0 / Z_0\)	Input exhausted; \(Z_0\) on top means all \(A\)’s were matched; accept

3. Verification that this is a DPDA:

   • Each \(\delta\) entry has exactly one output: condition 1 satisfied.
   • The \(\varepsilon\)-transition \(\delta(p_2, \varepsilon, Z_0) = (p_3, Z_0)\) uses stack top \(Z_0\). No input-reading transition from \(p_2\) has \(Z_0\) on top: condition 2 satisfied.

4. Trace for input \("aabb"\):

   Step	State	Remaining Input	Stack	Rule
   1	\(p_0\)	\(\mathbf{a}abb\)	\(Z_0\)	\(a,\,Z_0/AZ_0\): push \(A\)
   2	\(p_1\)	\(\mathbf{a}bb\)	\(A, Z_0\)	\(a,\,A/AA\): push \(A\)
   3	\(p_1\)	\(\mathbf{b}b\)	\(A, A, Z_0\)	\(b,\,A/\varepsilon\): pop \(A\)
   4	\(p_2\)	\(\mathbf{b}\)	\(A, Z_0\)	\(b,\,A/\varepsilon\): pop \(A\)
   5	\(p_2\)	\(\varepsilon\)	\(Z_0\)	\(\varepsilon,\,Z_0/Z_0\): accept
   6	\(p_3\)	\(\varepsilon\)	\(Z_0\)	ACCEPT \(\checkmark\)

   Full configuration sequence: \[(p_0, aabb, Z_0) \vdash (p_1, abb, AZ_0) \vdash (p_1, bb, AAZ_0) \vdash (p_2, b, AZ_0) \vdash (p_2, \varepsilon, Z_0) \vdash (p_3, \varepsilon, Z_0)\]

Answer: The DPDA with states \(p_0, p_1, p_2, p_3\) (accepting) and the transitions above recognizes \(L_1 = \{a^n b^n \mid n \geq 1\}\).

4.9. Construct a DPDA for \(L_2 = \{a^n b a^n \mid n \in \mathbb{N}^+\}\) (Tutorial 6, Example 3)

Construct a DPDA that recognizes \(L_2 = \{a^n b a^n \mid n \geq 1\}\).

Click to see the solution

Key Concept: Push one \(A\) per \(a\) before the \(b\). The single \(b\) is a pivot — it signals to switch from push mode to pop mode. After the \(b\), pop one \(A\) per \(a\) on the right side. Equal stacks before and after \(b\) means equal \(a\)-counts.

1. PDA specification:

   • States: \(q_0\) (start, push phase), \(q_1\) (pop phase, after \(b\)), \(q_2\) (accepting)
   • Stack alphabet: \(\Gamma = \{Z_0, A\}\)

2. Transitions:

   Transition	Notation	Meaning
   \(q_0 \circlearrowleft\)	\(a,\, Z_0 / AZ_0\)	First \(a\) before \(b\): push \(A\)
   \(q_0 \circlearrowleft\)	\(a,\, A / AA\)	Each subsequent \(a\) before \(b\): push \(A\)
   \(q_0 \to q_1\)	\(b,\, A / A\)	Read the \(b\): keep stack unchanged, switch to pop phase
   \(q_1 \circlearrowleft\)	\(a,\, A / \varepsilon\)	Each \(a\) after \(b\): pop one \(A\)
   \(q_1 \to q_2\)	\(\varepsilon,\, Z_0 / Z_0\)	All \(A\)’s matched; accept

3. Trace for input \("aba"\):

   • \(q_0 \xrightarrow{a,\,Z_0/AZ_0} q_0\): stack = \(A, Z_0\)
   • \(q_0 \xrightarrow{b,\,A/A} q_1\): stack = \(A, Z_0\) (unchanged)
   • \(q_1 \xrightarrow{a,\,A/\varepsilon} q_1\): stack = \(Z_0\)
   • \(q_1 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_2\): ACCEPT \(\checkmark\)

4. Trace for input \("aabaa"\):

   • \(q_0 \xrightarrow{a,\,Z_0/AZ_0} q_0\): stack = \(A, Z_0\)
   • \(q_0 \xrightarrow{a,\,A/AA} q_0\): stack = \(A, A, Z_0\)
   • \(q_0 \xrightarrow{b,\,A/A} q_1\): stack = \(A, A, Z_0\)
   • \(q_1 \xrightarrow{a,\,A/\varepsilon} q_1\): stack = \(A, Z_0\)
   • \(q_1 \xrightarrow{a,\,A/\varepsilon} q_1\): stack = \(Z_0\)
   • \(q_1 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_2\): ACCEPT \(\checkmark\)

Answer: The DPDA with states \(q_0, q_1, q_2\) (accepting) and the transitions above recognizes \(L_2 = \{a^n b a^n \mid n \geq 1\}\).

4.10. Construct a DPDA for \(L_3 = \{vcv^R \mid v \in \{a,b\}^*\}\) (Tutorial 6, Example 4)

Construct a DPDA that recognizes \(L_3 = \{vcv^R \mid v \in \{a,b\}^*\}\), where \(v^R\) denotes the reverse of \(v\) and \(c\) is a special separator symbol. The input alphabet is \(I = \{a, b, c\}\).

Click to see the solution

Key Concept: Push every symbol of \(v\) onto the stack (using distinct symbols \(A\) for \(a\) and \(B\) for \(b\)). When the center \(c\) is seen, switch to pop mode. Then match each symbol of \(v^R\) against the stack. Since \(v^R\) is the reverse of \(v\), the stack contents should match \(v^R\) from top to bottom.

1. PDA specification:

   • States: \(q_0\) (push phase), \(q_1\) (pop phase), \(q_2\) (accepting)
   • Stack alphabet: \(\Gamma = \{Z_0, A, B\}\) where \(A\) represents \(a\) and \(B\) represents \(b\)

2. Transitions:

   Push phase (\(q_0\), self-loops — push symbols of \(v\)):

   Notation	Meaning
   \(a,\, Z_0 / AZ_0\)	First \(a\): push \(A\)
   \(b,\, Z_0 / BZ_0\)	First \(b\): push \(B\)
   \(a,\, A / AA\)	Subsequent \(a\) with \(A\) on top: push \(A\)
   \(a,\, B / AB\)	Subsequent \(a\) with \(B\) on top: push \(A\)
   \(b,\, A / BA\)	Subsequent \(b\) with \(A\) on top: push \(B\)
   \(b,\, B / BB\)	Subsequent \(b\) with \(B\) on top: push \(B\)

   Pivot (on reading \(c\), move \(q_0 \to q_1\), keep stack unchanged):

   Notation	Meaning
   \(c,\, Z_0 / Z_0\)	\(v\) was empty: switch to pop mode
   \(c,\, A / A\)	\(c\) seen with \(A\) on top: switch to pop mode
   \(c,\, B / B\)	\(c\) seen with \(B\) on top: switch to pop mode

   Pop phase (\(q_1\), self-loops — match \(v^R\)):

   Notation	Meaning
   \(a,\, A / \varepsilon\)	Read \(a\), top is \(A\): match, pop \(A\)
   \(b,\, B / \varepsilon\)	Read \(b\), top is \(B\): match, pop \(B\)

   Accept: \(q_1 \to q_2\): \(\varepsilon,\, Z_0 / Z_0\) — all matched, accept.

3. Trace for input \("abcba"\) (so \(v = "ab"\), \(v^R = "ba"\)):

   • \(q_0 \xrightarrow{a,\,Z_0/AZ_0} q_0\): stack = \(A, Z_0\)
   • \(q_0 \xrightarrow{b,\,A/BA} q_0\): stack = \(B, A, Z_0\)
   • \(q_0 \xrightarrow{c,\,B/B} q_1\): stack = \(B, A, Z_0\) (unchanged)
   • \(q_1 \xrightarrow{b,\,B/\varepsilon} q_1\): stack = \(A, Z_0\)
   • \(q_1 \xrightarrow{a,\,A/\varepsilon} q_1\): stack = \(Z_0\)
   • \(q_1 \xrightarrow{\varepsilon,\,Z_0/Z_0} q_2\): ACCEPT \(\checkmark\)

Answer: The DPDA with states \(q_0, q_1, q_2\) (accepting) and the transitions above recognizes \(L_3 = \{vcv^R \mid v \in \{a,b\}^*\}\).